package org.liaohailong.helloworld.linkedlist;

/**
 * Author: liaohailong
 * Time: 2021/5/13 11:40
 * Describe:
 */
public class LinkedListSolution {

//    public boolean hasCycle(ListNode head) {
//        if (head == null || head.next == null) return false;
//
//        HashMap<ListNode, Integer> map = new HashMap<>();
//
//        int pos = 0;
//        ListNode node = head;
//        while (node != null) {
//            if (map.containsKey(node)) {
//                System.out.println("node.val = " + node.val);
//                return true;
//            }
//            map.put(node, pos);
//            node = node.next;
//            pos++;
//        }
//
//        return false;
//    }

    // 快慢指针，检查链表是否是环结构
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != slow) {
            if (fast == null || fast.next == null) return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

    // 找到入环第一个节点
//    public ListNode detectCycle(ListNode head) {
//        if (head == null || head.next == null) return null;
//
//        HashMap<ListNode, Integer> map = new HashMap<>();
//
//        int pos = 0;
//        ListNode node = head;
//        while (node != null) {
//            if (map.containsKey(node)) {
//                System.out.println("node.val = " + node.val);
//                return node;
//            }
//            map.put(node, pos);
//            node = node.next;
//            pos++;
//        }
//
//        return null;
//    }

    // 找到入环第一个节点
//    public ListNode detectCycle(ListNode head) {
//        if (head == null || head.next == null) return null;
//        ListNode slow = head, fast = head;
//
//        while (slow != null && fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if (slow == fast) break;
//        }
//        //如果满足下面的条件，说明无环
//        if (fast == null || fast.next == null) return null;
//
//        //下面开始找环的入口节点
//        //刚才的循环 慢指针走了a + b (a是从开始到入口节点) 假设等于cnt
//        //          快指针走了 a + b + c + b (b + c = 环)，应该等于2 * cnt
//        //推导出 a = c，所以把慢指针再放到头节点，下一次快慢指针相遇的节点即环的入口节点
//        slow = head;
//        while (slow != null && fast != null) {
//            if (slow == fast) break;
//            slow = slow.next;
//            fast = fast.next;
//        }
//        return fast;
//    }


    // LC 相交链表
    // 假定两个链表没有循环
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        HashSet<ListNode> save = new HashSet<>();
//        ListNode node = headA;
//        while (node != null) {
//            save.add(node);
//            node = node.next;
//        }
//
//        node = headB;
//        while (node != null) {
//            if (save.contains(node)) {
//                return node;
//            }
//            save.add(node);
//            node = node.next;
//        }
//
//        return null;
//    }

    // LC 相交链表
    // 假定两个链表没有循环
    // 时间复杂度O(n) 空间复杂度O(1)
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;

        if (a == null || b == null) return null;

        while (a != b) {
            a = a.next;
            b = b.next;
            if (a == null && b == null) return null;
            if (a == null) a = headB;
            if (b == null) b = headA;
        }

        return a;
    }

    // LC 移除倒第N个节点
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        if (n < 1) return head;
//
//        Stack<ListNode> stack = new Stack<>();
//
//        ListNode node = head;
//        while (node != null) {
//            stack.push(node);
//            node = node.next;
//        }
//
//        // Out of bounds
//        if (n > stack.size()) return head;
//
//        ListNode remove = null;
//        while (n-- > 0) {
//            remove = stack.pop();
//        }
//
//        if (stack.isEmpty()) {
//            // remove head
//            return remove.next;
//        } else {
//            ListNode prev = stack.pop();
//            prev.next = remove.next;
//            return head;
//        }
//    }

    // LC 移除倒第N个节点
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        ListNode listNode = new ListNode(-1);
//        listNode.next = head;
//
//        ListNode fast = listNode;
//        ListNode slow = listNode;
//        while (n-- > 0) {
//            fast = fast.next;
//        }
//
//        while (fast.next != null) {
//            fast = fast.next;
//            slow = slow.next;
//        }
//
//        slow.next = slow.next.next;
//        return listNode.next;
//    }

    // LC 反转链表
//    public ListNode reverseList(ListNode head) {
//        if (head == null || head.next == null) return head;
//        ListNode temp = head.next;
//        head.next = null;
//        return _reverseList(temp, head);
//    }
//
//    private ListNode _reverseList(ListNode next, ListNode node) {
//        if (next.next == null) {
//            next.next = node;
//            return next;
//        } else {
//            ListNode temp = next.next;
//            next.next = node;
//            return _reverseList(temp, next);
//        }
//    }

    // LC 反转链表 - 非递归
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode result = head;
        ListNode node = head.next;
        head.next = null;
        ListNode temp;
        do {
            temp = node.next;
            node.next = result;
            result = node;
            node = temp;
        } while (node != null);

        return result;
    }


    // LC 移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        if (head.next == null) return head.val == val ? null : head;

        ListNode fake = new ListNode(-1);
        fake.next = head;
        ListNode node = fake;
        while (node.next != null) {
            if (node.next.val == val) {
                node.next = node.next.next;
            } else
                node = node.next;
        }

        return fake.next;
    }


    // LC 奇偶链表
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return head;

        ListNode oddHead = null; // 奇数头节点
        ListNode oddNode = null; // 奇数尾节点
        ListNode evenHead = null; // 偶数头节点
        ListNode evenNode = null; // 偶数尾节点

        ListNode node = head;
        while (true) {
            if (oddHead == null) {
                oddHead = node;
                oddNode = oddHead;
            } else {
                if (oddNode != null && node != null) {
                    oddNode.next = node;
                    oddNode = oddNode.next;
                }
            }

            if (evenHead == null) {
                evenHead = node.next;
                evenNode = evenHead;
            } else {
                if (evenNode != null && node != null) {
                    evenNode.next = node.next;
                    evenNode = evenNode.next;
                }
            }

            if (node != null && node.next != null)
                node = node.next.next;
            else break;
        }

        oddNode.next = evenHead;
        return oddHead;
    }

    // LC 回纹链表 - 双指针，反转链表
    public boolean isPalindrome(ListNode head) {
        if (head == null) return false;
        if (head.next == null) return true;

        // 回文数找出方案：
        // 1，快慢指针，截断链表
        // 2，反转后半部分链表，得到新链表
        // 3，新链表与前半部分链表遍历，新链表里面的内容逐一对应前半部分链表内容，表示符合回文条件
        // 4，恢复反转链表

        // 二分截断链表
        ListNode fast = head.next;
        ListNode slow = head;
        while (slow != null && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // p2比p1要短
        ListNode newHead = reverseList(slow.next);
        ListNode p1 = head;
        ListNode p2 = newHead;
        boolean res = true;
        while (res && p2 != null) {
            if (p1.val != p2.val) res = false;
            p1 = p1.next;
            p2 = p2.next;
        }

        slow.next = reverseList(newHead);
        return res;
    }


    // LC 合并两个有序链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode newNode = newHead;
        ListNode l1Node = l1;
        ListNode l2Node = l2;
        while (true) {
            ListNode min = null;
            if (l1Node != null && l2Node != null) {
                if (l1Node.val <= l2Node.val) {
                    min = l1Node;
                    l1Node = l1Node.next;
                } else {
                    min = l2Node;
                    l2Node = l2Node.next;
                }
            } else if (l1Node == null && l2Node != null) {
                min = l2Node;
                l2Node = l2Node.next;
            } else if (l1Node != null && l2Node == null) {
                min = l1Node;
                l1Node = l1Node.next;
            }

            if (min != null) {
                newNode.next = min;
                newNode = newNode.next;
            } else break;
        }

        return newHead.next;
    }


    // LC 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = new ListNode(-1);
        ListNode temp = head;
        int extra = 0;
        while (true) {
            ListNode next = null;
            if (l1 != null && l2 != null) {
                int res = l1.val + l2.val;
                if (extra > 0) {
                    res += extra;
                    extra = 0;
                }
                if (res >= 10) {
                    extra = (int) (res / 10f);
                    res = res % 10;
                }
                next = new ListNode(res);

                l1 = l1.next;
                l2 = l2.next;
            } else if (l1 != null && l2 == null) {
                int res = l1.val;
                if (extra > 0) {
                    res += extra;
                    extra = 0;
                }
                if (res >= 10) {
                    extra = (int) (res / 10f);
                    res = res % 10;
                }
                next = new ListNode(res);
                l1 = l1.next;
            } else if (l1 == null && l2 != null) {
                int res = l2.val;
                if (extra > 0) {
                    res += extra;
                    extra = 0;
                }
                if (res >= 10) {
                    extra = (int) (res / 10f);
                    res = res % 10;
                }
                next = new ListNode(res);
                l2 = l2.next;
            } else break;

            temp.next = next;
            temp = temp.next;
        }

        if (extra > 0) {
            temp.next = new ListNode(extra);
        }
        return head.next;
    }


    public ListNode create(int[] arr) {
        ListNode head = null;
        ListNode node = null;
        for (int i : arr) {
            if (head == null) {
                head = new ListNode(i);
                node = head;
            } else {
                node.next = new ListNode(i);
                node = node.next;
            }
        }
        return head;
    }

    public static final class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
